/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package pr2.cruce;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import pr2.cromosoma.CromosomaPVC;

/**
 *
 * @author Gonzalo Ortiz Jaureguizar (gortiz at software.imdea.org)
 */
public class ERX extends EstrategiaCruce<CromosomaPVC> {

    private final ArrayList<ArrayList<Integer>> tabla;
    private final int size;
    private final ArrayList<Integer> visitadas;

    public ERX(int size) {
        super(size);
        this.size = size;
        tabla = new ArrayList<ArrayList<Integer>>(size);

        for (int i = 0; i < size; i++) {
            tabla.add(new ArrayList<Integer>(4));
        }

        visitadas = new ArrayList<Integer>(size);
    }

    private void addVecino(List<Integer> padre, int ciudadActual, ArrayList<Integer> vecinos) {
        int index = padre.indexOf(ciudadActual);
        Integer vecino = padre.get((index + 1) % size); //el siguiente
        if (!vecinos.contains(vecino) && vecino != ciudadActual) {
            vecinos.add(vecino);
        }
        vecino = padre.get((index - 1 + size) % size); //el anterior
        if (!vecinos.contains(vecino) && vecino != ciudadActual) {
            vecinos.add(vecino);
        }
    }

    private void cargarTabla(List<Integer> p1, List<Integer> p2) {
        for (int i = 0; i < size; i++) {
            ArrayList<Integer> anexas = tabla.get(i);
            anexas.clear();

            addVecino(p1, i, anexas);
            addVecino(p2, i, anexas);
        }
    }

    private void ordenarSiguientes(List<Integer> siguientes) {
        Collections.shuffle(siguientes);
        Collections.sort(siguientes, new Comparator<Integer>() {

            public int compare(Integer o1, Integer o2) {
                return -(tabla.get(o1).size() - tabla.get(o2).size());
            }
        });
    }

    private Integer getCiudadInicial(List<Integer> p1) {
        return p1.get((int) (Math.random() * size));
    }

    /**
     * @return una lista ordenada de las ciudades candidatas a ser elegidas como siguientes
     * @param actual la ciudad actual
     */
    private List<Integer> calcularCiudadesSiguientes(Integer actual) {
        List<Integer> candidatas = new LinkedList<Integer>();
        //primero calculamos la menos conectada
        for (Integer ciudad : tabla.get(actual)) {
            if (!visitadas.contains(ciudad)) { //solo añadimos las ciudades no visitadas
                candidatas.add(ciudad);
            }
        }
        return candidatas;
    }

    /**
     * Rellena recursivamente el hijo pasado. Añade la ciudad pasada como argumento al cromosoma
     * en la posicion indicada y se llama recursivamente probando con los sucesores de la ciudad actual
     * @param hijo El hijo a modificar
     * @param ciudad La ciudad que estamos intentando insertar
     * @param posicion La 
     * @return si el cromosoma acaba siendo correcto o false en caso contrario
     */
    private boolean rellenarElemento(List<Integer> hijo, Integer ciudad, int posicion) {
        if(posicion >= hijo.size()) {
            return true;
        }
        List<Integer> candidatas = calcularCiudadesSiguientes(ciudad);
        hijo.set(posicion, ciudad);
        for (Integer siguiente : candidatas) {
            if (rellenarElemento(hijo, siguiente, posicion + 1)) {
                return true;
            }
        }
        return false;
    }

    /**
     * Presupone que hijo tiene los numeros iniciados
     * @param hijo 
     */
    private boolean rellenarHijo(List<Integer> hijo) {
        int ciudad = getCiudadInicial(hijo);
        int intentos = 0;
        while (intentos < size) {
            intentos++;
            ciudad = (ciudad + 1) % size;
            if (rellenarElemento(hijo, ciudad, 0)) { //exito!
                return true;
            }
        }
        return false;
    }

    @Override
    protected void cruzar(CromosomaPVC p1, CromosomaPVC p2, CromosomaPVC h1, CromosomaPVC h2) {
        cargarTabla(p1.getGenes(), p2.getGenes());
        boolean exito = false;

        exito = rellenarHijo(h1.getGenes());
        assert (exito && CromosomaPVC.isCorrecto(h1));
        
        exito = rellenarHijo(h2.getGenes());
        assert (exito && CromosomaPVC.isCorrecto(h2));
    }
}
